<?php
/**
 * User: helloJiu
 * Date: 2021/11/2
 * Time: 10:31
 */

namespace App\Algorithm\DP;


class LastStoneWeightII
{
    /**
     * https://leetcode-cn.com/problems/last-stone-weight-ii/
     * @param Integer[] $stones
     * @return Integer
     */
    function lastStoneWeightII($stones)
    {
        $sum = array_sum($stones);
        $half = ceil($sum / 2);
        $dp = [];
        for ($w = 0; $w <= $half; $w++) {
            $dp[$w] = 0;
        }

        for ($i = 1; $i <= count($stones); $i++) {
            for ($w = $half; $w > 0; $w--) {
                $remain_w = $w - $stones[$i - 1];
                // lastStoneWeightII([31,26,33,21,40]));
                if ($remain_w >= 0) {
                    $dp[$w] = max($dp[$w], $dp[$remain_w] + $stones[$i - 1]);
                }
            }
        }

        return abs(($dp[$half] - ($sum - $dp[$half])));

    }
}